{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Verbal Arithmetic Puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isSolvable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #口算难题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个方程，左边用&nbsp;<code>words</code>&nbsp;表示，右边用&nbsp;<code>result</code> 表示。</p>\n",
    "\n",
    "<p>你需要根据以下规则检查方程是否可解：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每个字符都会被解码成一位数字（0 - 9）。</li>\n",
    "\t<li>每对不同的字符必须映射到不同的数字。</li>\n",
    "\t<li>每个 <code>words[i]</code> 和 <code>result</code>&nbsp;都会被解码成一个没有前导零的数字。</li>\n",
    "\t<li>左侧数字之和（<code>words</code>）等于右侧数字（<code>result</code>）。&nbsp;</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果方程可解，返回&nbsp;<code>True</code>，否则返回&nbsp;<code>False</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>words = [&quot;SEND&quot;,&quot;MORE&quot;], result = &quot;MONEY&quot;\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>映射 &#39;S&#39;-&gt; 9, &#39;E&#39;-&gt;5, &#39;N&#39;-&gt;6, &#39;D&#39;-&gt;7, &#39;M&#39;-&gt;1, &#39;O&#39;-&gt;0, &#39;R&#39;-&gt;8, &#39;Y&#39;-&gt;&#39;2&#39;\n",
    "所以 &quot;SEND&quot; + &quot;MORE&quot; = &quot;MONEY&quot; ,  9567 + 1085 = 10652</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>words = [&quot;SIX&quot;,&quot;SEVEN&quot;,&quot;SEVEN&quot;], result = &quot;TWENTY&quot;\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>映射 &#39;S&#39;-&gt; 6, &#39;I&#39;-&gt;5, &#39;X&#39;-&gt;0, &#39;E&#39;-&gt;8, &#39;V&#39;-&gt;7, &#39;N&#39;-&gt;2, &#39;T&#39;-&gt;1, &#39;W&#39;-&gt;&#39;3&#39;, &#39;Y&#39;-&gt;4\n",
    "所以 &quot;SIX&quot; + &quot;SEVEN&quot; + &quot;SEVEN&quot; = &quot;TWENTY&quot; ,  650 + 68782 + 68782 = 138214</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>words = [&quot;THIS&quot;,&quot;IS&quot;,&quot;TOO&quot;], result = &quot;FUNNY&quot;\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>words = [&quot;LEET&quot;,&quot;CODE&quot;], result = &quot;POINT&quot;\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= words.length &lt;= 5</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length,&nbsp;results.length&nbsp;&lt;= 7</code></li>\n",
    "\t<li><code>words[i], result</code>&nbsp;只含有大写英文字母</li>\n",
    "\t<li>表达式中使用的不同字符数最大为&nbsp;10</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [verbal-arithmetic-puzzle](https://leetcode.cn/problems/verbal-arithmetic-puzzle/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [verbal-arithmetic-puzzle](https://leetcode.cn/problems/verbal-arithmetic-puzzle/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"SEND\",\"MORE\"]\\n\"MONEY\"', '[\"SIX\",\"SEVEN\",\"SEVEN\"]\\n\"TWENTY\"', '[\"LEET\",\"CODE\"]\\n\"POINT\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSolvable(self, words: List[str], result: str) -> bool:\n",
    "        used, carry = [False] * 10, [0] * 10\n",
    "        lead_zero, rep = dict(), dict()\n",
    "\n",
    "        for word in words:\n",
    "            if len(word) > len(result):\n",
    "                return False\n",
    "            for ch in word:\n",
    "                rep[ch] = -1\n",
    "                lead_zero[ch] = max(lead_zero.get(ch, 0), 0)\n",
    "            if len(word) > 1:\n",
    "                lead_zero[word[0]] = 1\n",
    "        for ch in result:\n",
    "            rep[ch] = -1\n",
    "            lead_zero[ch] = max(lead_zero.get(ch, 0), 0)\n",
    "        if len(result) > 1:\n",
    "            lead_zero[result[0]] = 1\n",
    "        \n",
    "        def dfs(pos, iden, length):\n",
    "            if pos == length:\n",
    "                return carry[pos] == 0\n",
    "            elif iden < len(words):\n",
    "                sz = len(words[iden])\n",
    "                if sz < pos or rep[words[iden][sz - pos - 1]] != -1:\n",
    "                    return dfs(pos, iden + 1, length)\n",
    "                else:\n",
    "                    ch = words[iden][sz - pos - 1]\n",
    "                    for i in range(lead_zero[ch], 10):\n",
    "                        if not used[i]:\n",
    "                            used[i], rep[ch] = True, i\n",
    "                            check = dfs(pos, iden + 1, length)\n",
    "                            used[i], rep[ch] = False, -1\n",
    "                            if check:\n",
    "                                return True\n",
    "                    return False\n",
    "            else:\n",
    "                left = carry[pos] + sum(rep[word[len(word) - pos - 1]] for word in words if len(word) > pos)\n",
    "                carry[pos + 1], left = left // 10, left % 10\n",
    "                ch = result[len(result) - pos - 1]\n",
    "                if rep[ch] == left:\n",
    "                    return dfs(pos + 1, 0, length)\n",
    "                elif rep[ch] == -1 and not used[left] and not (lead_zero[ch] == 1 and left == 0):\n",
    "                    used[left], rep[ch] = True, left\n",
    "                    check = dfs(pos + 1, 0, length)\n",
    "                    used[left], rep[ch] = False, -1\n",
    "                    return check\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "        return dfs(0, 0, len(result))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSolvable(self, words: List[str], result: str) -> bool:\n",
    "        _weight = dict()\n",
    "        _lead_zero = set()\n",
    "        for word in words:\n",
    "            for i, ch in enumerate(word[::-1]):\n",
    "                _weight[ch] = _weight.get(ch, 0) + 10**i\n",
    "            if len(word) > 1:\n",
    "                _lead_zero.add(word[0])\n",
    "        for i, ch in enumerate(result[::-1]):\n",
    "            _weight[ch] = _weight.get(ch, 0) - 10**i\n",
    "        if len(result) > 1:\n",
    "            _lead_zero.add(result[0])\n",
    "        \n",
    "        weight = sorted(list(_weight.items()), key=lambda x: -abs(x[1]))\n",
    "        suffix_sum_min = [0] * len(weight)\n",
    "        suffix_sum_max = [0] * len(weight)\n",
    "        for i in range(len(weight)):\n",
    "            suffix_pos = sorted(x[1] for x in weight[i:] if x[1] > 0)\n",
    "            suffix_neg = sorted(x[1] for x in weight[i:] if x[1] < 0)\n",
    "            suffix_sum_min[i] = sum((len(suffix_pos) - 1 - j) * elem for j, elem in enumerate(suffix_pos)) + sum((9 - j) * elem for j, elem in enumerate(suffix_neg))\n",
    "            suffix_sum_max[i] = sum((10 - len(suffix_pos) + j) * elem for j, elem in enumerate(suffix_pos)) + sum(j * elem for j, elem in enumerate(suffix_neg))\n",
    "        \n",
    "        lead_zero = [int(ch in _lead_zero) for (ch, _) in weight]\n",
    "        used = [0] * 10\n",
    "        \n",
    "        def dfs(pos, total):\n",
    "            if pos == len(weight):\n",
    "                return total == 0\n",
    "            if not total + suffix_sum_min[pos] <= 0 <= total + suffix_sum_max[pos]:\n",
    "                return False\n",
    "            for i in range(lead_zero[pos], 10):\n",
    "                if not used[i]:\n",
    "                    used[i] = True\n",
    "                    if dfs(pos + 1, total + weight[pos][1] * i):\n",
    "                        return True\n",
    "                    used[i] = False\n",
    "            return False\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSolvable(self, words: List[str], result: str) -> bool:\n",
    "        _weight = dict()\n",
    "        _lead_zero = set()\n",
    "        for word in words:\n",
    "            for i, ch in enumerate(word[::-1]):\n",
    "                _weight[ch] = _weight.get(ch, 0) + 10**i\n",
    "            if len(word) > 1:\n",
    "                _lead_zero.add(word[0])\n",
    "        for i, ch in enumerate(result[::-1]):\n",
    "            _weight[ch] = _weight.get(ch, 0) - 10**i\n",
    "        if len(result) > 1:\n",
    "            _lead_zero.add(result[0])\n",
    "        \n",
    "        weight = sorted(list(_weight.items()), key=lambda x: -abs(x[1]))\n",
    "        suffix_sum_min = [0] * len(weight)\n",
    "        suffix_sum_max = [0] * len(weight)\n",
    "        for i in range(len(weight)):\n",
    "            suffix_pos = sorted(x[1] for x in weight[i:] if x[1] > 0)\n",
    "            suffix_neg = sorted(x[1] for x in weight[i:] if x[1] < 0)\n",
    "            suffix_sum_min[i] = sum((len(suffix_pos) - 1 - j) * elem for j, elem in enumerate(suffix_pos)) + sum((9 - j) * elem for j, elem in enumerate(suffix_neg))\n",
    "            suffix_sum_max[i] = sum((10 - len(suffix_pos) + j) * elem for j, elem in enumerate(suffix_pos)) + sum(j * elem for j, elem in enumerate(suffix_neg))\n",
    "        \n",
    "        lead_zero = [int(ch in _lead_zero) for (ch, _) in weight]\n",
    "        used = [0] * 10\n",
    "        \n",
    "        def dfs(pos, total):\n",
    "            if pos == len(weight):\n",
    "                return total == 0\n",
    "            if not total + suffix_sum_min[pos] <= 0 <= total + suffix_sum_max[pos]:\n",
    "                return False\n",
    "            for i in range(lead_zero[pos], 10):\n",
    "                if not used[i]:\n",
    "                    used[i] = True\n",
    "                    check = dfs(pos + 1, total + weight[pos][1] * i)\n",
    "                    used[i] = False\n",
    "                    if check:\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "权值合并\n",
    "\n",
    "SEND  =             S * 1000 + E * 100 + N * 10 + D\n",
    "MORE  =             M * 1000 + O * 100 + R * 10 + E\n",
    "MONEY = M * 10000 + O * 1000 + N * 100 + E * 10 + Y\n",
    "\n",
    "S * 1000 + E * 91 - N * 90 + D - M * 9000 - O * 900 + R * 10 - Y = 0\n",
    "系数为正：S * 1000 + E * 91 + R * 10 + D\n",
    "系数为负：-(O * 900 + N * 90 + Y)\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def isSolvable(self, words: List[str], result: str) -> bool:\n",
    "        _weight = dict()\n",
    "        _lead_zero = set()\n",
    "        for word in words:\n",
    "            for i, ch in enumerate(word[::-1]):\n",
    "                _weight[ch] = _weight.get(ch, 0) + 10**i\n",
    "            if len(word) > 1:\n",
    "                _lead_zero.add(word[0])\n",
    "        for i, ch in enumerate(result[::-1]):\n",
    "            _weight[ch] = _weight.get(ch, 0) - 10**i\n",
    "        if len(result) > 1:\n",
    "            _lead_zero.add(result[0])\n",
    "        \n",
    "        weight = sorted(list(_weight.items()), key=lambda x: -abs(x[1]))\n",
    "        suffix_sum_min = [0] * len(weight)\n",
    "        suffix_sum_max = [0] * len(weight)\n",
    "        for i in range(len(weight)):\n",
    "            suffix_pos = sorted(x[1] for x in weight[i:] if x[1] > 0)\n",
    "            suffix_neg = sorted(x[1] for x in weight[i:] if x[1] < 0)\n",
    "            suffix_sum_min[i] = sum((len(suffix_pos) - 1 - j) * elem for j, elem in enumerate(suffix_pos)) + sum((9 - j) * elem for j, elem in enumerate(suffix_neg))\n",
    "            suffix_sum_max[i] = sum((10 - len(suffix_pos) + j) * elem for j, elem in enumerate(suffix_pos)) + sum(j * elem for j, elem in enumerate(suffix_neg))\n",
    "        \n",
    "        lead_zero = [int(ch in _lead_zero) for (ch, _) in weight]\n",
    "        used = [0] * 10\n",
    "        \n",
    "        def dfs(pos, total):\n",
    "            if pos == len(weight):\n",
    "                return total == 0\n",
    "            if not total + suffix_sum_min[pos] <= 0 <= total + suffix_sum_max[pos]:\n",
    "                return False\n",
    "            for i in range(lead_zero[pos], 10):\n",
    "                if not used[i]:\n",
    "                    used[i] = True\n",
    "                    check = dfs(pos + 1, total + weight[pos][1] * i)\n",
    "                    used[i] = False\n",
    "                    if check:\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSolvable(self, words: List[str], result: str) -> bool:\n",
    "\n",
    "        no_zero = set()\n",
    "        for word in words + [result]:\n",
    "            if len(word) > len(result):\n",
    "                return False\n",
    "            if len(word) != 1:\n",
    "                no_zero.add(word[0])\n",
    "\n",
    "        words = [word[::-1] for word in words]\n",
    "        result = result[::-1]\n",
    "\n",
    "        hashmap = defaultdict(lambda :-1)\n",
    "\n",
    "        pos = [[] for _ in range(len(result))]\n",
    "        for word in words + [result]:\n",
    "            for i , w in enumerate(word):\n",
    "                pos[i].append(w)\n",
    "        n = len(result)\n",
    "\n",
    "        def dfs(i,state,p):\n",
    "            if i == n:return p == 0\n",
    "            other = [x for x in range(10) if state & (1 << x)]\n",
    "            nonlocal hashmap\n",
    "            t = copy.deepcopy(hashmap)\n",
    "            xx = list(set([x for x in pos[i] if x not in hashmap]))\n",
    "            for x in permutations(other,len(xx)):\n",
    "                nxt_state = state\n",
    "                y = 0\n",
    "                for idx , j in enumerate(x):\n",
    "                    if j == 0 and xx[idx] in no_zero:break\n",
    "                    hashmap[xx[idx]] = j\n",
    "                    nxt_state ^= (1 << j)\n",
    "                else:\n",
    "                    for w in pos[i]:\n",
    "                        y += hashmap[w]\n",
    "                    z = hashmap[result[i]]\n",
    "                    if z != (y-z+p)%10:\n",
    "                        continue\n",
    "                    if dfs(i+1,nxt_state,(y-z+p)//10):\n",
    "                        return True\n",
    "                hashmap = copy.deepcopy(t)\n",
    "            return False\n",
    "        return dfs(0,2**10-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSolvable(self, words: List[str], result: str) -> bool:\n",
    "        wd=[]\n",
    "        allwd=words+[result]\n",
    "        ml=0\n",
    "        for i in range(len(allwd)):\n",
    "            ml=max(ml,len(allwd[i]))\n",
    "        print(allwd)\n",
    "        wdset=set()\n",
    "        dt=dict()\n",
    "        visited=set()\n",
    "        pre=list()\n",
    "        for i in range(1,ml+1):\n",
    "            for j in allwd:\n",
    "                if i<=len(j) and j[-i] not in wdset:\n",
    "                    wdset.add(j[-i])\n",
    "                    wd.append(j[-i])\n",
    "                if len(j)!=1:\n",
    "                    pre.append(j[0])\n",
    "        if len(result)!=1:\n",
    "            pre.append(result[0])\n",
    "        pre=list(set(pre))\n",
    "        print(\"pre\",pre)\n",
    "        def valid():\n",
    "            # if dt.get('S',-1)==9 and dt.get('E',-1)==5 and dt.get('N',-1)==6 and dt.get('D',-1)==7 and dt.get('M',-1)==1 and dt.get('O',-1)==0 and  dt.get('O',-1)==8 and dt.get('O',-1)==2:\n",
    "            #     print(\"=====\")\n",
    "            #0 前置检查 开始不能为0\n",
    "            for i in range(len(pre)):\n",
    "                if dt.get(pre[i],-1)==0:\n",
    "                    return -1\n",
    "            #1.检查所有是否都有匹配\n",
    "            flag=True\n",
    "            for w in wd:\n",
    "                if dt.get(w,-1)==-1:\n",
    "                    flag=False\n",
    "                    break\n",
    "            if flag: #所有都有匹配了！ 检查加起来是否相等\n",
    "                left=[]\n",
    "                for i in range(len(words)):\n",
    "                    t=''\n",
    "                    for j in range(len(words[i])):\n",
    "                        t=t+str(dt[words[i][j]])\n",
    "                    left.append(int(t))\n",
    "                right=''\n",
    "                for i in range(len(result)):\n",
    "                    right=right+str(dt[result[i]])\n",
    "                if sum(left)==int(right):\n",
    "                    print(dt)\n",
    "                    return 1\n",
    "                else:\n",
    "                    return -1\n",
    "            \n",
    "            else:\n",
    "                i=1 #倒数第n列\n",
    "                tmp=[0]*10\n",
    "                while(1):\n",
    "                    t=0\n",
    "                    for word in words:\n",
    "                        if i>len(word):\n",
    "                            j=0\n",
    "                        else:\n",
    "                            j=dt.get(word[-i],-1)\n",
    "                        if j==-1:\n",
    "                            return 0\n",
    "                        t=t+j\n",
    "                    t=t+tmp[-i]\n",
    "                    if i>len(result):\n",
    "                        jj=0\n",
    "                    else:\n",
    "                        jj=dt.get(result[-i],-1)\n",
    "                    if jj==-1:\n",
    "                        return 0\n",
    "                    if t%10 != jj:\n",
    "                        return -1\n",
    "                    else:\n",
    "                        tmp[-i-1]=t//10\n",
    "                        i+=1\n",
    "                        continue\n",
    "                    \n",
    "\n",
    "\n",
    "        def f(i):\n",
    "            v=valid()\n",
    "            if v==-1:\n",
    "                return False\n",
    "            if i==len(wdset):\n",
    "                return v==1\n",
    "            for j in range(0,10):\n",
    "                if j not in visited:\n",
    "                    visited.add(j)\n",
    "                    dt[wd[i]]=j\n",
    "                    if f(i+1):\n",
    "                        return True\n",
    "                    dt[wd[i]]=-1\n",
    "                    visited.remove(j)\n",
    "            return False\n",
    "        return f(0)\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isSolvable(self, words, result: str) -> bool:\n",
    "        # 边界情况绝对无解\n",
    "        if all(len(word)+1 < len(result) for word in words):\n",
    "            return False\n",
    "        # 建立方程\n",
    "        dct = defaultdict(int)\n",
    "        for word in words:\n",
    "            k = len(word)\n",
    "            for i in range(k):\n",
    "                dct[word[i]] += 10**(k-i-1)\n",
    "        n = len(result)\n",
    "        for i in range(n):\n",
    "            dct[result[i]] -= 10 ** (n - i - 1)\n",
    "        # 按照系数的绝对值大小进行逆排序并去掉零系数的项\n",
    "        lst = [[dct[k], k] for k in dct if dct[k]]\n",
    "        lst.sort(key=lambda x: abs(x[0]), reverse=True)\n",
    "        m = len(lst)\n",
    "\n",
    "        # 计算剩余序列的最大值与最小值\n",
    "        def compute_ceil_floor(rest, pos, neg):\n",
    "            post_ceil = 0\n",
    "            for r in range(len(neg)):\n",
    "                post_ceil += rest[r]*neg[r]\n",
    "            for r in range(len(pos)):\n",
    "                post_ceil += rest[-r-1]*pos[r]\n",
    "            post_floor = 0\n",
    "            for r in range(len(pos)):\n",
    "                post_floor += rest[r]*pos[r]\n",
    "            for r in range(len(neg)):\n",
    "                post_floor += rest[-r-1]*neg[r]\n",
    "            return post_ceil, post_floor\n",
    "\n",
    "        # 检查该映射是否存在前导零\n",
    "        def check():\n",
    "            map_num = dict()\n",
    "            for c in range(m):\n",
    "                map_num[lst[c][1]] = mapping[c]\n",
    "            for word in words+[result]:\n",
    "                if len(word) >= 2:\n",
    "                    # 映射为前导零\n",
    "                    if word[0] in map_num and map_num[word[0]] == 0:\n",
    "                        return False\n",
    "                    # 首字母方程系数为0可选任意剩余值若剩余为0则不符合\n",
    "                    if word[0] not in map_num and m == 9 and 0 not in mapping:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        # 深搜寻找可能的映射\n",
    "        ans = []\n",
    "        mapping = [-1]*m\n",
    "\n",
    "        def dfs(pre_sum, ind):\n",
    "            nonlocal ans\n",
    "            # 搜寻到存在的解就停止\n",
    "            if ans:\n",
    "                return\n",
    "            if ind == m:\n",
    "                if not pre_sum and check():\n",
    "                    ans = mapping[:]\n",
    "                return\n",
    "            for num in range(10):\n",
    "                if num not in mapping:\n",
    "                    # 计算选定当前值的情况下后续可能的最大最小值是否还能满足和为0\n",
    "                    rest = [j for j in range(10) if j not in mapping and j!=num]\n",
    "                    rest.sort()\n",
    "                    pos = [ls[0] for ls in lst[ind+1:] if ls[0] > 0]\n",
    "                    neg = [ls[0] for ls in lst[ind+1:] if ls[0] < 0]\n",
    "                    post_ceil, post_floor = compute_ceil_floor(rest, pos, neg)\n",
    "                    # 剪枝\n",
    "                    if -post_ceil <= pre_sum + lst[ind][0] * num <= -post_floor:\n",
    "                        mapping[ind] = num\n",
    "                        dfs(pre_sum + lst[ind][0]*num, ind+1)\n",
    "                        # 回溯\n",
    "                        mapping[ind] = -1\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return True if ans else False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSolvable(self, words: List[str], result: str) -> bool:\n",
    "        if any(len(w) > len(result) for w in words):\n",
    "            return False\n",
    "        def dfs(i, add, used):\n",
    "            if i == len(result):\n",
    "                return add == 0\n",
    "            need = set([w[i] for w in words + [result] if i < len(w) and w[i] not in used])\n",
    "            can = set(range(10)) - set(used.values())\n",
    "            for sub in permutations(can, len(need)):\n",
    "                used.update(dict(zip(need, sub)))\n",
    "                if all(i != len(w) - 1 or len(w) == 1 or used[w[i]] != 0 for w in words + [result]):\n",
    "                    s = sum(used[w[i]] for w in words if i < len(w))\n",
    "                    add2, s = divmod(s + add, 10)\n",
    "                    if s == used[result[i]] and dfs(i + 1, add2, used):\n",
    "                        return True\n",
    "                for c in need:\n",
    "                    del used[c]\n",
    "            return False\n",
    "\n",
    "\n",
    "        words = [w[::-1] for w in words]\n",
    "        result = result[::-1]\n",
    "        return dfs(0, 0, {})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isSolvable(self, words, result: str) -> bool:\n",
    "        # 边界情况绝对无解\n",
    "        if all(len(word)+1 < len(result) for word in words):\n",
    "            return False\n",
    "        # 建立方程\n",
    "        dct = defaultdict(int)\n",
    "        for word in words:\n",
    "            k = len(word)\n",
    "            for i in range(k):\n",
    "                dct[word[i]] += 10**(k-i-1)\n",
    "        n = len(result)\n",
    "        for i in range(n):\n",
    "            dct[result[i]] -= 10 ** (n - i - 1)\n",
    "        # 按照系数的绝对值大小进行逆排序并去掉零系数的项\n",
    "        lst = [[dct[k], k] for k in dct if dct[k]]\n",
    "        lst.sort(key=lambda x: abs(x[0]), reverse=True)\n",
    "        m = len(lst)\n",
    "\n",
    "        # 计算剩余序列的最大值与最小值\n",
    "        def compute_ceil_floor(rest, pos, neg):\n",
    "            post_ceil = 0\n",
    "            for r in range(len(neg)):\n",
    "                post_ceil += rest[r]*neg[r]\n",
    "            for r in range(len(pos)):\n",
    "                post_ceil += rest[-r-1]*pos[r]\n",
    "            post_floor = 0\n",
    "            for r in range(len(pos)):\n",
    "                post_floor += rest[r]*pos[r]\n",
    "            for r in range(len(neg)):\n",
    "                post_floor += rest[-r-1]*neg[r]\n",
    "            return post_ceil, post_floor\n",
    "\n",
    "        # 检查该映射是否存在前导零\n",
    "        def check():\n",
    "            map_num = dict()\n",
    "            for c in range(m):\n",
    "                map_num[lst[c][1]] = mapping[c]\n",
    "            for word in words+[result]:\n",
    "                if len(word) >= 2:\n",
    "                    # 映射为前导零\n",
    "                    if word[0] in map_num and map_num[word[0]] == 0:\n",
    "                        return False\n",
    "                    # 首字母方程系数为0可选任意剩余值若剩余为0则不符合\n",
    "                    if word[0] not in map_num and m == 9 and 0 not in mapping:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        # 深搜寻找可能的映射\n",
    "        ans = []\n",
    "        mapping = [-1]*m\n",
    "\n",
    "        def dfs(pre_sum, ind):\n",
    "            nonlocal ans\n",
    "            # 搜寻到存在的解就停止\n",
    "            if ans:\n",
    "                return\n",
    "            if ind == m:\n",
    "                if not pre_sum and check():\n",
    "                    ans = mapping[:]\n",
    "                return\n",
    "            for num in range(10):\n",
    "                if num not in mapping:\n",
    "                    # 计算选定当前值的情况下后续可能的最大最小值是否还能满足和为0\n",
    "                    rest = [j for j in range(10) if j not in mapping and j!=num]\n",
    "                    rest.sort()\n",
    "                    pos = [ls[0] for ls in lst[ind+1:] if ls[0] > 0]\n",
    "                    neg = [ls[0] for ls in lst[ind+1:] if ls[0] < 0]\n",
    "                    post_ceil, post_floor = compute_ceil_floor(rest, pos, neg)\n",
    "                    # 剪枝\n",
    "                    if -post_ceil <= pre_sum + lst[ind][0] * num <= -post_floor:\n",
    "                        mapping[ind] = num\n",
    "                        dfs(pre_sum + lst[ind][0]*num, ind+1)\n",
    "                        # 回溯\n",
    "                        mapping[ind] = -1\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return True if ans else False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def isSolvable(self, words: List[str], result: str) -> bool:\n",
    "class Solution:\n",
    "    def isSolvable(self, words: List[str], result: str) -> bool:\n",
    "        _weight = dict()\n",
    "        _lead_zero = set()\n",
    "        for word in words:\n",
    "            for i, ch in enumerate(word[::-1]):\n",
    "                _weight[ch] = _weight.get(ch, 0) + 10 ** i\n",
    "            if len(word) > 1:\n",
    "                _lead_zero.add(word[0])\n",
    "        for i, ch in enumerate(result[::-1]):\n",
    "            _weight[ch] = _weight.get(ch, 0) - 10 ** i\n",
    "        if len(result) > 1:\n",
    "            _lead_zero.add(result[0])\n",
    "\n",
    "        weight = sorted(list(_weight.items()), key=lambda x: -abs(x[1]))\n",
    "        suffix_sum_min = [0] * len(weight)\n",
    "        suffix_sum_max = [0] * len(weight)\n",
    "        for i in range(len(weight)):\n",
    "            suffix_pos = sorted(x[1] for x in weight[i:] if x[1] > 0)\n",
    "            suffix_neg = sorted(x[1] for x in weight[i:] if x[1] < 0)\n",
    "            suffix_sum_min[i] = sum(\n",
    "                (len(suffix_pos) - 1 - j) * elem for j, elem in enumerate(suffix_pos)\n",
    "            ) + sum((9 - j) * elem for j, elem in enumerate(suffix_neg))\n",
    "            suffix_sum_max[i] = sum(\n",
    "                (10 - len(suffix_pos) + j) * elem for j, elem in enumerate(suffix_pos)\n",
    "            ) + sum(j * elem for j, elem in enumerate(suffix_neg))\n",
    "\n",
    "        lead_zero = [int(ch in _lead_zero) for (ch, _) in weight]\n",
    "        used = [0] * 10\n",
    "\n",
    "        def dfs(pos, total):\n",
    "            if pos == len(weight):\n",
    "                return total == 0\n",
    "            if not total + suffix_sum_min[pos] <= 0 <= total + suffix_sum_max[pos]:\n",
    "                return False\n",
    "            for i in range(lead_zero[pos], 10):\n",
    "                if not used[i]:\n",
    "                    used[i] = True\n",
    "                    check = dfs(pos + 1, total + weight[pos][1] * i)\n",
    "                    used[i] = False\n",
    "                    if check:\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        return dfs(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def isSolvable(self, words: List[str], result: str) -> bool:\n",
    "        # 边界情况绝对无解\n",
    "        if all(len(word) + 1 < len(result) for word in words):\n",
    "            return False\n",
    "        wc = Counter()\n",
    "        n_zero = set()  # 列出不能为0的字母\n",
    "        for word in words:\n",
    "            if len(word) > 1: n_zero.add(word[0])\n",
    "            for i in range(len(word) - 1, -1, -1):\n",
    "                wc[word[i]] += 10**(len(word) - 1 - i)\n",
    "        for i in range(len(result) - 1, -1, -1):\n",
    "            wc[result[i]] -= 10**(len(result) - 1 - i)\n",
    "        if len(result) > 1: n_zero.add(result[0])\n",
    "        n = len(wc)\n",
    "        arr = sorted([[v, k] for k, v in wc.items()], key=lambda x: -abs(x[0]))\n",
    "\n",
    "        used = [False] * 10\n",
    "\n",
    "        def calc_range(i):\n",
    "            # 预判后续可能性，计算出剩余的可能最大最小值\n",
    "            ss = sorted([ii for ii in range(10) if not used[ii]], reverse=True)  # 可用数字大-小\n",
    "            po = [arr[ii][0] for ii in range(i, n) if arr[ii][0] > 0]  # 正系数\n",
    "            ng = [arr[ii][0] for ii in range(i, n) if arr[ii][0] < 0]  # 负系数\n",
    "            mn, mx = 0, 0\n",
    "            for a, b in zip(po, ss):\n",
    "                mx += a * b\n",
    "            for a, b in zip(ng, ss[::-1]):\n",
    "                mx += a * b\n",
    "            for a, b in zip(ng, ss):\n",
    "                mn += a * b\n",
    "            for a, b in zip(po, ss[::-1]):\n",
    "                mn += a * b\n",
    "            return mx, mn\n",
    "\n",
    "        def dfs(i, sm):\n",
    "            if i == n: return sm == 0\n",
    "            mx, mn = calc_range(i)  # 利用后续可能性进行剪枝\n",
    "            if sm + mx < 0 or sm + mn > 0: return False\n",
    "            for v in range(1 if arr[i][1] in n_zero else 0, 10):\n",
    "                if used[v]: continue\n",
    "                used[v] = True\n",
    "                if dfs(i + 1, sm + arr[i][0] * v): return True\n",
    "                used[v] = False\n",
    "            return False\n",
    "\n",
    "        return dfs(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSolvable(self, words: List[str], result: str) -> bool:\n",
    "        used, carry = [False] * 10, [0] * 10\n",
    "        lead_zero, rep = dict(), dict()\n",
    "\n",
    "        for word in words:\n",
    "            if len(word) > len(result):\n",
    "                return False\n",
    "            for ch in word:\n",
    "                rep[ch] = -1\n",
    "                lead_zero[ch] = max(lead_zero.get(ch, 0), 0)\n",
    "            if len(word) > 1:\n",
    "                lead_zero[word[0]] = 1\n",
    "        for ch in result:\n",
    "            rep[ch] = -1\n",
    "            lead_zero[ch] = max(lead_zero.get(ch, 0), 0)\n",
    "        if len(result) > 1:\n",
    "            lead_zero[result[0]] = 1\n",
    "        \n",
    "        def dfs(pos, iden, length):\n",
    "            if pos == length:\n",
    "                return carry[pos] == 0\n",
    "            elif iden < len(words):\n",
    "                sz = len(words[iden])\n",
    "                if sz < pos or rep[words[iden][sz - pos - 1]] != -1:\n",
    "                    return dfs(pos, iden + 1, length)\n",
    "                else:\n",
    "                    ch = words[iden][sz - pos - 1]\n",
    "                    for i in range(lead_zero[ch], 10):\n",
    "                        if not used[i]:\n",
    "                            used[i], rep[ch] = True, i\n",
    "                            check = dfs(pos, iden + 1, length)\n",
    "                            used[i], rep[ch] = False, -1\n",
    "                            if check:\n",
    "                                return True\n",
    "                    return False\n",
    "            else:\n",
    "                left = carry[pos] + sum(rep[word[len(word) - pos - 1]] for word in words if len(word) > pos)\n",
    "                carry[pos + 1], left = left // 10, left % 10\n",
    "                ch = result[len(result) - pos - 1]\n",
    "                if rep[ch] == left:\n",
    "                    return dfs(pos + 1, 0, length)\n",
    "                elif rep[ch] == -1 and not used[left] and not (lead_zero[ch] == 1 and left == 0):\n",
    "                    used[left], rep[ch] = True, left\n",
    "                    check = dfs(pos + 1, 0, length)\n",
    "                    used[left], rep[ch] = False, -1\n",
    "                    return check\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "        return dfs(0, 0, len(result))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isSolvable(self, words: List[str], result: str) -> bool:\n",
    "        _weight = collections.defaultdict(int)\n",
    "        _lead_zero = set()\n",
    "        for word in words:\n",
    "            for i, ch in enumerate(word[::-1]):\n",
    "                _weight[ch] += 10 ** i\n",
    "            if len(word) > 1:\n",
    "                _lead_zero.add(word[0])\n",
    "\n",
    "        for i, ch in enumerate(result[::-1]):\n",
    "            _weight[ch] -= 10 ** i\n",
    "        if len(result) > 1:\n",
    "            _lead_zero.add(result[0])\n",
    "\n",
    "        # dict_items([('D', 1), ('N', -90), ('E', 91), ('S', 1000), ('R', 10), ('O', -900), ('M', -9000), ('Y', -1)])\n",
    "        # [('M', -9000), ('S', 1000), ('O', -900), ('E', 91), ('N', -90), ('R', 10), ('D', 1), ('Y', -1)]\n",
    "        weight = sorted(list(_weight.items()), key=lambda x: -abs(x[1]))\n",
    "\n",
    "        n = len(weight)\n",
    "        suffix_sum_min = [0] * n\n",
    "        suffix_sum_max = [0] * n\n",
    "        for i in range(n):\n",
    "            suffix_pos = sorted(x[1] for x in weight[i:] if x[1] > 0)\n",
    "            suffix_neg = sorted(x[1] for x in weight[i:] if x[1] < 0)\n",
    "            # -- suffix_pos [1, 10, 91, 1000]\n",
    "            # -- suffix_neg [-9000, -900, -90, -1]\n",
    "\n",
    "            suffix_sum_min[i] = sum(\n",
    "                (len(suffix_pos) - 1 - j) * v for j, v in enumerate(suffix_pos)\n",
    "            ) + sum((9 - j) * v for j, v in enumerate(suffix_neg))\n",
    "            suffix_sum_max[i] = sum(\n",
    "                (10 - len(suffix_pos) + j) * v for j, v in enumerate(suffix_pos)\n",
    "            ) + sum(j * v for j, v in enumerate(suffix_neg))\n",
    "\n",
    "        lead_zero = [int(ch in _lead_zero) for (ch, _) in weight]\n",
    "        used = [0] * 10\n",
    "\n",
    "        def dfs(pos, total):\n",
    "            if pos == len(weight):\n",
    "                return total == 0\n",
    "\n",
    "            # if total < suffix_sum_min[pos] or total > suffix_sum_max[pos]:\n",
    "            # if not total + suffix_sum_min[pos] <= 0 <= total + suffix_sum_max[pos]:\n",
    "            if suffix_sum_min[pos] > -total or -total > suffix_sum_max[pos]:\n",
    "                return False\n",
    "\n",
    "            for i in range(lead_zero[pos], 10):\n",
    "                if not used[i]:\n",
    "                    used[i] = 1\n",
    "                    check = dfs(pos + 1, total + weight[pos][1] * i)\n",
    "                    used[i] = 0\n",
    "                    if check:\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        return dfs(0, 0)\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def isSolvable(self, words: List[str], result: str) -> bool:\n",
    "#         _weight = dict()\n",
    "#         _lead_zero = set()\n",
    "#         for word in words:\n",
    "#             for i, ch in enumerate(word[::-1]):\n",
    "#                 _weight[ch] = _weight.get(ch, 0) + 10 ** i\n",
    "#             if len(word) > 1:\n",
    "#                 _lead_zero.add(word[0])\n",
    "\n",
    "#         _weight1 = dict()\n",
    "#         _lead_zero1 = set()\n",
    "#         print(_weight, _lead_zero)\n",
    "#         for i, ch in enumerate(result[::-1]):\n",
    "#             _weight[ch] = _weight.get(ch, 0) - 10 ** i\n",
    "#             _weight1[ch] = _weight1.get(ch, 0) - 10 ** i\n",
    "#         if len(result) > 1:\n",
    "#             _lead_zero.add(result[0])\n",
    "#             _lead_zero1.add(result[0])\n",
    "#         print(_weight1, _lead_zero1)\n",
    "#         print(_weight, _lead_zero)\n",
    "\n",
    "#         weight = sorted(list(_weight.items()), key=lambda x: -abs(x[1]))\n",
    "#         print(_weight.items())\n",
    "#         print(weight)\n",
    "#         suffix_sum_min = [0] * len(weight)\n",
    "#         suffix_sum_max = [0] * len(weight)\n",
    "#         for i in range(len(weight)):\n",
    "#             suffix_pos = sorted(x[1] for x in weight[i:] if x[1] > 0)\n",
    "#             suffix_neg = sorted(x[1] for x in weight[i:] if x[1] < 0)\n",
    "#             print(\"-- suffix_pos\", suffix_pos)\n",
    "#             print(\"-- suffix_neg\", suffix_neg)\n",
    "\n",
    "#             suffix_sum_min[i] = sum(\n",
    "#                 (len(suffix_pos) - 1 - j) * elem for j, elem in enumerate(suffix_pos)\n",
    "#             ) + sum((9 - j) * elem for j, elem in enumerate(suffix_neg))\n",
    "\n",
    "#             suffix_sum_max[i] = sum(\n",
    "#                 (10 - len(suffix_pos) + j) * elem for j, elem in enumerate(suffix_pos)\n",
    "#             ) + sum(j * elem for j, elem in enumerate(suffix_neg))\n",
    "\n",
    "#         lead_zero = [int(ch in _lead_zero) for (ch, _) in weight]\n",
    "#         used = [0] * 10\n",
    "\n",
    "#         def dfs(pos, total):\n",
    "#             if pos == len(weight):\n",
    "#                 return total == 0\n",
    "#             if not total + suffix_sum_min[pos] <= 0 <= total + suffix_sum_max[pos]:\n",
    "#                 return False\n",
    "#             for i in range(lead_zero[pos], 10):\n",
    "#                 if not used[i]:\n",
    "#                     used[i] = True\n",
    "#                     check = dfs(pos + 1, total + weight[pos][1] * i)\n",
    "#                     used[i] = False\n",
    "#                     if check:\n",
    "#                         return True\n",
    "#             return False\n",
    "\n",
    "#         return dfs(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSolvable(self, words, result: str) -> bool:\n",
    "        # 边界情况绝对无解\n",
    "        if all(len(word)+1 < len(result) for word in words):\n",
    "            return False\n",
    "        # 建立方程\n",
    "        dct = defaultdict(int)\n",
    "        for word in words:\n",
    "            k = len(word)\n",
    "            for i in range(k):\n",
    "                dct[word[i]] += 10**(k-i-1)\n",
    "        n = len(result)\n",
    "        for i in range(n):\n",
    "            dct[result[i]] -= 10 ** (n - i - 1)\n",
    "        # 按照系数的绝对值大小进行逆排序并去掉零系数的项\n",
    "        lst = [[dct[k], k] for k in dct if dct[k]]\n",
    "        lst.sort(key=lambda x: abs(x[0]), reverse=True)\n",
    "        m = len(lst)\n",
    "\n",
    "        # 计算剩余序列的最大值与最小值\n",
    "        def compute_ceil_floor(rest, pos, neg):\n",
    "            post_ceil = 0\n",
    "            for r in range(len(neg)):\n",
    "                post_ceil += rest[r]*neg[r]\n",
    "            for r in range(len(pos)):\n",
    "                post_ceil += rest[-r-1]*pos[r]\n",
    "            post_floor = 0\n",
    "            for r in range(len(pos)):\n",
    "                post_floor += rest[r]*pos[r]\n",
    "            for r in range(len(neg)):\n",
    "                post_floor += rest[-r-1]*neg[r]\n",
    "            return post_ceil, post_floor\n",
    "\n",
    "        # 检查该映射是否存在前导零\n",
    "        def check():\n",
    "            map_num = dict()\n",
    "            for c in range(m):\n",
    "                map_num[lst[c][1]] = mapping[c]\n",
    "            for word in words+[result]:\n",
    "                if len(word) >= 2:\n",
    "                    # 映射为前导零\n",
    "                    if word[0] in map_num and map_num[word[0]] == 0:\n",
    "                        return False\n",
    "                    # 首字母方程系数为0可选任意剩余值若剩余为0则不符合\n",
    "                    if word[0] not in map_num and m == 9 and 0 not in mapping:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        # 深搜寻找可能的映射\n",
    "        ans = []\n",
    "        mapping = [-1]*m\n",
    "\n",
    "        def dfs(pre_sum, ind):\n",
    "            nonlocal ans\n",
    "            # 搜寻到存在的解就停止\n",
    "            if ans:\n",
    "                return\n",
    "            if ind == m:\n",
    "                if not pre_sum and check():\n",
    "                    ans = mapping[:]\n",
    "                return\n",
    "            for num in range(10):\n",
    "                if num not in mapping:\n",
    "                    # 计算选定当前值的情况下后续可能的最大最小值是否还能满足和为0\n",
    "                    rest = [j for j in range(10) if j not in mapping and j!=num]\n",
    "                    rest.sort()\n",
    "                    pos = [ls[0] for ls in lst[ind+1:] if ls[0] > 0]\n",
    "                    neg = [ls[0] for ls in lst[ind+1:] if ls[0] < 0]\n",
    "                    post_ceil, post_floor = compute_ceil_floor(rest, pos, neg)\n",
    "                    # 剪枝\n",
    "                    if -post_ceil <= pre_sum + lst[ind][0] * num <= -post_floor:\n",
    "                        mapping[ind] = num\n",
    "                        dfs(pre_sum + lst[ind][0]*num, ind+1)\n",
    "                        # 回溯\n",
    "                        mapping[ind] = -1\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return True if ans else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isSolvable(self, words: List[str], result: str) -> bool:\n",
    "        _weight = collections.defaultdict(int)\n",
    "        _lead_zero = set()\n",
    "        for word in words:\n",
    "            for i, ch in enumerate(word[::-1]):\n",
    "                _weight[ch] += 10 ** i\n",
    "            if len(word) > 1:\n",
    "                _lead_zero.add(word[0])\n",
    "\n",
    "        for i, ch in enumerate(result[::-1]):\n",
    "            _weight[ch] -= 10 ** i\n",
    "        if len(result) > 1:\n",
    "            _lead_zero.add(result[0])\n",
    "\n",
    "        # dict_items([('D', 1), ('N', -90), ('E', 91), ('S', 1000), ('R', 10), ('O', -900), ('M', -9000), ('Y', -1)])\n",
    "        # [('M', -9000), ('S', 1000), ('O', -900), ('E', 91), ('N', -90), ('R', 10), ('D', 1), ('Y', -1)]\n",
    "        weight = sorted(list(_weight.items()), key=lambda x: -abs(x[1]))\n",
    "\n",
    "        n = len(weight)\n",
    "        suffix_sum_min = [0] * n\n",
    "        suffix_sum_max = [0] * n\n",
    "        for i in range(n):\n",
    "            suffix_pos = sorted(x[1] for x in weight[i:] if x[1] > 0)\n",
    "            suffix_neg = sorted(x[1] for x in weight[i:] if x[1] < 0)\n",
    "            # -- suffix_pos [1, 10, 91, 1000]\n",
    "            # -- suffix_neg [-9000, -900, -90, -1]\n",
    "\n",
    "            suffix_sum_min[i] = sum(\n",
    "                (len(suffix_pos) - 1 - j) * v for j, v in enumerate(suffix_pos)\n",
    "            ) + sum((9 - j) * v for j, v in enumerate(suffix_neg))\n",
    "            suffix_sum_max[i] = sum(\n",
    "                (10 - len(suffix_pos) + j) * v for j, v in enumerate(suffix_pos)\n",
    "            ) + sum(j * v for j, v in enumerate(suffix_neg))\n",
    "\n",
    "        lead_zero = [int(ch in _lead_zero) for (ch, _) in weight]\n",
    "        used = [0] * 10\n",
    "\n",
    "        def dfs(pos, total):\n",
    "            if pos == len(weight):\n",
    "                return total == 0\n",
    "\n",
    "            # if total <= suffix_sum_min[pos] or total >= suffix_sum_max[pos]:\n",
    "            if not total + suffix_sum_min[pos] <= 0 <= total + suffix_sum_max[pos]:\n",
    "                return False\n",
    "\n",
    "            for i in range(lead_zero[pos], 10):\n",
    "                if not used[i]:\n",
    "                    used[i] = 1\n",
    "                    check = dfs(pos + 1, total + weight[pos][1] * i)\n",
    "                    used[i] = 0\n",
    "                    if check:\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        return dfs(0, 0)\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def isSolvable(self, words: List[str], result: str) -> bool:\n",
    "#         _weight = dict()\n",
    "#         _lead_zero = set()\n",
    "#         for word in words:\n",
    "#             for i, ch in enumerate(word[::-1]):\n",
    "#                 _weight[ch] = _weight.get(ch, 0) + 10 ** i\n",
    "#             if len(word) > 1:\n",
    "#                 _lead_zero.add(word[0])\n",
    "\n",
    "#         _weight1 = dict()\n",
    "#         _lead_zero1 = set()\n",
    "#         print(_weight, _lead_zero)\n",
    "#         for i, ch in enumerate(result[::-1]):\n",
    "#             _weight[ch] = _weight.get(ch, 0) - 10 ** i\n",
    "#             _weight1[ch] = _weight1.get(ch, 0) - 10 ** i\n",
    "#         if len(result) > 1:\n",
    "#             _lead_zero.add(result[0])\n",
    "#             _lead_zero1.add(result[0])\n",
    "#         print(_weight1, _lead_zero1)\n",
    "#         print(_weight, _lead_zero)\n",
    "\n",
    "#         weight = sorted(list(_weight.items()), key=lambda x: -abs(x[1]))\n",
    "#         print(_weight.items())\n",
    "#         print(weight)\n",
    "#         suffix_sum_min = [0] * len(weight)\n",
    "#         suffix_sum_max = [0] * len(weight)\n",
    "#         for i in range(len(weight)):\n",
    "#             suffix_pos = sorted(x[1] for x in weight[i:] if x[1] > 0)\n",
    "#             suffix_neg = sorted(x[1] for x in weight[i:] if x[1] < 0)\n",
    "#             print(\"-- suffix_pos\", suffix_pos)\n",
    "#             print(\"-- suffix_neg\", suffix_neg)\n",
    "\n",
    "#             suffix_sum_min[i] = sum(\n",
    "#                 (len(suffix_pos) - 1 - j) * elem for j, elem in enumerate(suffix_pos)\n",
    "#             ) + sum((9 - j) * elem for j, elem in enumerate(suffix_neg))\n",
    "\n",
    "#             suffix_sum_max[i] = sum(\n",
    "#                 (10 - len(suffix_pos) + j) * elem for j, elem in enumerate(suffix_pos)\n",
    "#             ) + sum(j * elem for j, elem in enumerate(suffix_neg))\n",
    "\n",
    "#         lead_zero = [int(ch in _lead_zero) for (ch, _) in weight]\n",
    "#         used = [0] * 10\n",
    "\n",
    "#         def dfs(pos, total):\n",
    "#             if pos == len(weight):\n",
    "#                 return total == 0\n",
    "#             if not total + suffix_sum_min[pos] <= 0 <= total + suffix_sum_max[pos]:\n",
    "#                 return False\n",
    "#             for i in range(lead_zero[pos], 10):\n",
    "#                 if not used[i]:\n",
    "#                     used[i] = True\n",
    "#                     check = dfs(pos + 1, total + weight[pos][1] * i)\n",
    "#                     used[i] = False\n",
    "#                     if check:\n",
    "#                         return True\n",
    "#             return False\n",
    "\n",
    "#         return dfs(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSolvable(self, W: List[str], R: str) -> bool:\n",
    "        n=len(W)\n",
    "        m=len(R)\n",
    "        ml=max(len(w) for w in W)\n",
    "        if m>ml+1 or ml>m:\n",
    "            return False\n",
    "        vis=set()\n",
    "        Map={}\n",
    "        def dfs(i,j,x):\n",
    "            '''\n",
    "            i:第i位\n",
    "            j:第j个数\n",
    "            x:进位\n",
    "            '''\n",
    "            if i > m:\n",
    "                print(Map,vis)\n",
    "                return not x\n",
    "            if j==n:\n",
    "                x1=x//10\n",
    "                x0=x%10\n",
    "                c=R[-i]\n",
    "                if c in Map:\n",
    "                    if x0!=Map[c]:\n",
    "                        return False\n",
    "                    if m>1 and i==m and not Map[c]:\n",
    "                        return False\n",
    "                    return dfs(i+1,0,x1)\n",
    "                if x0 not in vis:\n",
    "                    Map[c]=x0\n",
    "                    vis.add(x0)\n",
    "                    res = dfs(i+1,0,x1)\n",
    "                    del Map[c]\n",
    "                    vis.remove(x0)\n",
    "                    return res\n",
    "                else:\n",
    "                    return False\n",
    "            w=W[j]\n",
    "            lw=len(w)\n",
    "            if i>lw:\n",
    "                return dfs(i,j+1,x)\n",
    "            c=w[-i]\n",
    "            if c in Map:\n",
    "                if i>1 and i==lw and not Map[c]:\n",
    "                    return False\n",
    "                return dfs(i,j+1,x+Map[c])\n",
    "            for k in range(10):\n",
    "                if k in vis:\n",
    "                    continue\n",
    "                if i>1 and i==lw and not k:\n",
    "                    continue\n",
    "                Map[c]=k\n",
    "                vis.add(k)\n",
    "                res = dfs(i,j+1,x+k)\n",
    "                del Map[c]\n",
    "                vis.remove(k)\n",
    "                if res:\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(1,0,0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isSolvable(self, words: List[str], result: str) -> bool:\n",
    "        _weight = collections.defaultdict(int)\n",
    "        _lead_zero = set()\n",
    "        for word in words:\n",
    "            for i, ch in enumerate(word[::-1]):\n",
    "                _weight[ch] += 10 ** i\n",
    "            if len(word) > 1:\n",
    "                _lead_zero.add(word[0])\n",
    "\n",
    "        for i, ch in enumerate(result[::-1]):\n",
    "            _weight[ch] -= 10 ** i\n",
    "        if len(result) > 1:\n",
    "            _lead_zero.add(result[0])\n",
    "\n",
    "        # dict_items([('D', 1), ('N', -90), ('E', 91), ('S', 1000), ('R', 10), ('O', -900), ('M', -9000), ('Y', -1)])\n",
    "        # [('M', -9000), ('S', 1000), ('O', -900), ('E', 91), ('N', -90), ('R', 10), ('D', 1), ('Y', -1)]\n",
    "        weight = sorted(list(_weight.items()), key=lambda x: -abs(x[1]))\n",
    "\n",
    "        n = len(weight)\n",
    "        suffix_sum_min = [0] * n\n",
    "        suffix_sum_max = [0] * n\n",
    "        for i in range(n):\n",
    "            suffix_pos = sorted(x[1] for x in weight[i:] if x[1] > 0)\n",
    "            suffix_neg = sorted(x[1] for x in weight[i:] if x[1] < 0)\n",
    "            # -- suffix_pos [1, 10, 91, 1000]\n",
    "            # -- suffix_neg [-9000, -900, -90, -1]\n",
    "\n",
    "            suffix_sum_min[i] = sum(\n",
    "                (len(suffix_pos) - 1 - j) * v for j, v in enumerate(suffix_pos)\n",
    "            ) + sum((9 - j) * v for j, v in enumerate(suffix_neg))\n",
    "            suffix_sum_max[i] = sum(\n",
    "                (10 - len(suffix_pos) + j) * v for j, v in enumerate(suffix_pos)\n",
    "            ) + sum(j * v for j, v in enumerate(suffix_neg))\n",
    "\n",
    "        lead_zero = [int(ch in _lead_zero) for (ch, _) in weight]\n",
    "        used = [0] * 10\n",
    "\n",
    "        def dfs(pos, total):\n",
    "            if pos == len(weight):\n",
    "                return total == 0\n",
    "\n",
    "            # if total < suffix_sum_min[pos] or total > suffix_sum_max[pos]:\n",
    "            # if not total + suffix_sum_min[pos] <= 0 <= total + suffix_sum_max[pos]:\n",
    "            # 取值范围为 [-max', -min'] = [-9712, 8713]\n",
    "            # if suffix_sum_min[pos] > -total or -total > suffix_sum_max[pos]:\n",
    "            if suffix_sum_min[pos] > -total:\n",
    "                return False\n",
    "\n",
    "            for i in range(lead_zero[pos], 10):\n",
    "                if not used[i]:\n",
    "                    used[i] = 1\n",
    "                    check = dfs(pos + 1, total + weight[pos][1] * i)\n",
    "                    used[i] = 0\n",
    "                    if check:\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        return dfs(0, 0)\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def isSolvable(self, words: List[str], result: str) -> bool:\n",
    "#         _weight = dict()\n",
    "#         _lead_zero = set()\n",
    "#         for word in words:\n",
    "#             for i, ch in enumerate(word[::-1]):\n",
    "#                 _weight[ch] = _weight.get(ch, 0) + 10 ** i\n",
    "#             if len(word) > 1:\n",
    "#                 _lead_zero.add(word[0])\n",
    "\n",
    "#         _weight1 = dict()\n",
    "#         _lead_zero1 = set()\n",
    "#         print(_weight, _lead_zero)\n",
    "#         for i, ch in enumerate(result[::-1]):\n",
    "#             _weight[ch] = _weight.get(ch, 0) - 10 ** i\n",
    "#             _weight1[ch] = _weight1.get(ch, 0) - 10 ** i\n",
    "#         if len(result) > 1:\n",
    "#             _lead_zero.add(result[0])\n",
    "#             _lead_zero1.add(result[0])\n",
    "#         print(_weight1, _lead_zero1)\n",
    "#         print(_weight, _lead_zero)\n",
    "\n",
    "#         weight = sorted(list(_weight.items()), key=lambda x: -abs(x[1]))\n",
    "#         print(_weight.items())\n",
    "#         print(weight)\n",
    "#         suffix_sum_min = [0] * len(weight)\n",
    "#         suffix_sum_max = [0] * len(weight)\n",
    "#         for i in range(len(weight)):\n",
    "#             suffix_pos = sorted(x[1] for x in weight[i:] if x[1] > 0)\n",
    "#             suffix_neg = sorted(x[1] for x in weight[i:] if x[1] < 0)\n",
    "#             print(\"-- suffix_pos\", suffix_pos)\n",
    "#             print(\"-- suffix_neg\", suffix_neg)\n",
    "\n",
    "#             suffix_sum_min[i] = sum(\n",
    "#                 (len(suffix_pos) - 1 - j) * elem for j, elem in enumerate(suffix_pos)\n",
    "#             ) + sum((9 - j) * elem for j, elem in enumerate(suffix_neg))\n",
    "\n",
    "#             suffix_sum_max[i] = sum(\n",
    "#                 (10 - len(suffix_pos) + j) * elem for j, elem in enumerate(suffix_pos)\n",
    "#             ) + sum(j * elem for j, elem in enumerate(suffix_neg))\n",
    "\n",
    "#         lead_zero = [int(ch in _lead_zero) for (ch, _) in weight]\n",
    "#         used = [0] * 10\n",
    "\n",
    "#         def dfs(pos, total):\n",
    "#             if pos == len(weight):\n",
    "#                 return total == 0\n",
    "#             if not total + suffix_sum_min[pos] <= 0 <= total + suffix_sum_max[pos]:\n",
    "#                 return False\n",
    "#             for i in range(lead_zero[pos], 10):\n",
    "#                 if not used[i]:\n",
    "#                     used[i] = True\n",
    "#                     check = dfs(pos + 1, total + weight[pos][1] * i)\n",
    "#                     used[i] = False\n",
    "#                     if check:\n",
    "#                         return True\n",
    "#             return False\n",
    "\n",
    "#         return dfs(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def isSolvable(self, words: List[str], result: str) -> bool:\n",
    "        char_map = collections.defaultdict(lambda: - 1)\n",
    "        not_zero = collections.defaultdict(lambda: 0)\n",
    "        used = [0] * 10\n",
    "        for w in words:\n",
    "            if len(w) > 1:\n",
    "                not_zero[w[0]] = 1 \n",
    "            if len(w) > len(result):\n",
    "                return False \n",
    "        if len(result) > 1:\n",
    "            not_zero[result[0]] = 1 \n",
    "        carry = [0] * (len(result) + 1)\n",
    "        def dfs(pos, index):\n",
    "            if pos == len(result):\n",
    "                return carry[pos] == 0\n",
    "            if index < len(words):\n",
    "                curW = words[index]\n",
    "                curLen = len(curW)\n",
    "                if pos > curLen or char_map[curW[curLen - pos - 1]] != - 1:\n",
    "                    return dfs(pos, index + 1)\n",
    "                curC = curW[curLen - pos - 1]\n",
    "                for i in range(not_zero[curC], 10):\n",
    "                    if used[i]:\n",
    "                        continue\n",
    "                    used[i] = 1 \n",
    "                    char_map[curC] = i\n",
    "                    if dfs(pos, index + 1):\n",
    "                        return True \n",
    "                    used[i] = 0\n",
    "                    char_map[curC] = - 1\n",
    "                else:\n",
    "                    return False \n",
    "            else:\n",
    "                curSum = sum(char_map[w[len(w) - pos - 1]] for w in words if len(w) > pos) + carry[pos]\n",
    "                carry[pos + 1] = curSum // 10 \n",
    "                curVal = curSum % 10 \n",
    "                curC= result[len(result) - pos - 1]\n",
    "                if char_map[curC] == curVal:\n",
    "                    return dfs(pos + 1, 0)\n",
    "                elif char_map[curC] != -1:\n",
    "                    return False \n",
    "                else:\n",
    "                    if not used[curVal] and not (curVal == 0 and not_zero[curC]):\n",
    "                        used[curVal] = 1 \n",
    "                        char_map[curC] = curVal\n",
    "                        if dfs(pos + 1, 0):\n",
    "                            return True \n",
    "                        used[curVal] = 0\n",
    "                        char_map[curC] = - 1\n",
    "                        return False \n",
    "                return False \n",
    "                \n",
    "        return dfs(0, 0)\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def isSolvable(self, words: List[str], result: str) -> bool:\n",
    "        alp2num = collections.defaultdict(list)\n",
    "        n = len(words)\n",
    "        m = []\n",
    "        words.append(result)\n",
    "        for word in words:\n",
    "            m.append(len(word))\n",
    "\n",
    "            for iw,w in enumerate(word):\n",
    "\n",
    "                if iw==0 and len(word)>1:\n",
    "                    alp2num[w] = [True,-1]\n",
    "                else:\n",
    "                    if w in alp2num.keys() and alp2num[w][0]==True:\n",
    "                        alp2num[w] = [True,-1]\n",
    "                    else:\n",
    "                        alp2num[w] = [False,-1]\n",
    "                    \n",
    "        print(alp2num)\n",
    "        for ix,x in enumerate(words):\n",
    "            words[ix] = x[::-1]\n",
    "        result = result[::-1]\n",
    "\n",
    "        nums = set([0,1,2,3,4,5,6,7,8,9])\n",
    "        usedNum = set([])\n",
    "\n",
    "        def getPosRange(i,j):\n",
    "            \n",
    "            if alp2num[words[j][i]][1]==-1:\n",
    "                if alp2num[words[j][i]][0]:\n",
    "                    trange = nums.difference(usedNum).difference(set([0]))\n",
    "                else:\n",
    "                    trange = nums.difference(usedNum)\n",
    "            else:\n",
    "                trange = [alp2num[words[j][i]][1]]\n",
    "            return sorted(trange)\n",
    "\n",
    "        def dfs(i,j,carry):\n",
    "            if i>=len(words[j]) and j<n:\n",
    "                return dfs(i,j+1,carry)\n",
    "            if j<n:\n",
    "                trange = getPosRange(i,j)\n",
    "                for v in trange:\n",
    "                    if alp2num[words[j][i]][1]==-1:\n",
    "                        flag = 0\n",
    "                    else:\n",
    "                        flag = 1\n",
    "                    if flag==0:\n",
    "                        alp2num[words[j][i]][1] = v\n",
    "                        usedNum.add(v)\n",
    "                    if dfs(i,j+1,carry):\n",
    "                        return True\n",
    "                    if flag==0:\n",
    "                        alp2num[words[j][i]][1] = -1\n",
    "                        usedNum.discard(v)\n",
    "                return False\n",
    "            \n",
    "            if j==n:\n",
    "                return judge(i,carry)\n",
    "              \n",
    "                \n",
    "        def judge(i,carry):\n",
    "\n",
    "            res = 0\n",
    "            for k in range(n):\n",
    "                if i>=len(words[k]):\n",
    "                    continue\n",
    "                res = res+alp2num[words[k][i]][1]\n",
    "            res = res+carry\n",
    "            v = res%10\n",
    "            carry = res//10\n",
    "            if i<len(result):\n",
    "                if alp2num[result[i]][0] ==  True and v==0:\n",
    "                    return False\n",
    "                if alp2num[result[i]][1]==-1 and v not in usedNum:\n",
    "                    alp2num[result[i]][1] = v\n",
    "                    usedNum.add(v)\n",
    "                    if dfs(i+1,0,carry):\n",
    "                        return True\n",
    "                    else:\n",
    "                        alp2num[result[i]][1] = -1\n",
    "                        usedNum.discard(v)\n",
    "                        return False\n",
    "                if alp2num[result[i]][1]==v:\n",
    "                    if dfs(i+1,0,carry):\n",
    "                        return True\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if res!=0:\n",
    "                    return False\n",
    "                else:\n",
    "                    return True\n",
    "\n",
    "        r = dfs(0,0,0)\n",
    "\n",
    "        return r\n",
    "                \n",
    "\n",
    "                        \n",
    "\n",
    "\n",
    "                        \n",
    "                        \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def isSolvable(self, words: List[str], result: str) -> bool:\n",
    "        char_map = collections.defaultdict(lambda: - 1)\n",
    "        not_zero = collections.defaultdict(lambda: 0)\n",
    "        used = [0] * 10\n",
    "        for w in words:\n",
    "            if len(w) > 1:\n",
    "                not_zero[w[0]] = 1 \n",
    "            if len(w) > len(result):\n",
    "                return False \n",
    "        if len(result) > 1:\n",
    "            not_zero[result[0]] = 1 \n",
    "        carry = [0] * (len(result) + 1)\n",
    "        def dfs(pos, index):\n",
    "            if pos == len(result):\n",
    "                return carry[pos] == 0\n",
    "            if index < len(words):\n",
    "                curW = words[index]\n",
    "                curLen = len(curW)\n",
    "                if pos > curLen or char_map[curW[curLen - pos - 1]] != - 1:\n",
    "                    return dfs(pos, index + 1)\n",
    "                curC = curW[curLen - pos - 1]\n",
    "                for i in range(not_zero[curC], 10):\n",
    "                    if used[i]:\n",
    "                        continue\n",
    "                    used[i] = 1 \n",
    "                    char_map[curC] = i\n",
    "                    if dfs(pos, index + 1):\n",
    "                        return True \n",
    "                    used[i] = 0\n",
    "                    char_map[curC] = - 1\n",
    "                else:\n",
    "                    return False \n",
    "            \n",
    "            \n",
    "            else:\n",
    "                curSum = sum(char_map[w[len(w) - pos - 1]] for w in words if len(w) > pos) + carry[pos]\n",
    "                carry[pos + 1] = curSum // 10 \n",
    "                curVal = curSum % 10 \n",
    "                curC= result[len(result) - pos - 1]\n",
    "                if char_map[curC] == curVal:\n",
    "                    return dfs(pos + 1, 0)\n",
    "                elif char_map[curC] != -1:\n",
    "                    return False \n",
    "                else:\n",
    "                    if not used[curVal] and not (curVal == 0 and not_zero[curC]):\n",
    "                        used[curVal] = 1 \n",
    "                        char_map[curC] = curVal\n",
    "                        if dfs(pos + 1, 0):\n",
    "                            return True \n",
    "                        used[curVal] = 0\n",
    "                        char_map[curC] = - 1\n",
    "                        return False \n",
    "                return False \n",
    "                \n",
    "        return dfs(0, 0)\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSolvable(self, words: List[str], result: str) -> bool:\n",
    "        wd=[]\n",
    "        allwd=words+[result]\n",
    "        ml=0\n",
    "        for i in range(len(allwd)):\n",
    "            ml=max(ml,len(allwd[i]))\n",
    "        print(allwd)\n",
    "        wdset=set()\n",
    "        dt=dict()\n",
    "        visited=set()\n",
    "        pre=list()\n",
    "        for i in range(1,ml+1):\n",
    "            for j in allwd:\n",
    "                if i<=len(j) and j[-i] not in wdset:\n",
    "                    wdset.add(j[-i])\n",
    "                    wd.append(j[-i])\n",
    "                if len(j)!=1:\n",
    "                    pre.append(j[0])\n",
    "        if len(result)!=1:\n",
    "            pre.append(result[0])\n",
    "        pre=list(set(pre))\n",
    "        print(\"pre\",pre)\n",
    "        def valid():\n",
    "            # if dt.get('S',-1)==9 and dt.get('E',-1)==5 and dt.get('N',-1)==6 and dt.get('D',-1)==7 and dt.get('M',-1)==1 and dt.get('O',-1)==0 and  dt.get('O',-1)==8 and dt.get('O',-1)==2:\n",
    "            #     print(\"=====\")\n",
    "            #0 前置检查 开始不能为0\n",
    "            for i in range(len(pre)):\n",
    "                if dt.get(pre[i],-1)==0:\n",
    "                    return -1\n",
    "            #1.检查所有是否都有匹配\n",
    "            flag=True\n",
    "            for w in wd:\n",
    "                if dt.get(w,-1)==-1:\n",
    "                    flag=False\n",
    "                    break\n",
    "            if flag: #所有都有匹配了！ 检查加起来是否相等\n",
    "                left=[]\n",
    "                for i in range(len(words)):\n",
    "                    t=''\n",
    "                    for j in range(len(words[i])):\n",
    "                        t=t+str(dt[words[i][j]])\n",
    "                    left.append(int(t))\n",
    "                right=''\n",
    "                for i in range(len(result)):\n",
    "                    right=right+str(dt[result[i]])\n",
    "                if sum(left)==int(right):\n",
    "                    print(dt)\n",
    "                    return 1\n",
    "                else:\n",
    "                    return -1\n",
    "            \n",
    "            else:\n",
    "                i=1 #倒数第n列\n",
    "                tmp=[0]*10\n",
    "                while(1):\n",
    "                    t=0\n",
    "                    for word in words:\n",
    "                        if i>len(word):\n",
    "                            j=0\n",
    "                        else:\n",
    "                            j=dt.get(word[-i],-1)\n",
    "                        if j==-1:\n",
    "                            return 0\n",
    "                        t=t+j\n",
    "                    t=t+tmp[-i]\n",
    "                    if i>len(result):\n",
    "                        jj=0\n",
    "                    else:\n",
    "                        jj=dt.get(result[-i],-1)\n",
    "                    if jj==-1:\n",
    "                        return 0\n",
    "                    if t%10 != jj:\n",
    "                        return -1\n",
    "                    else:\n",
    "                        tmp[-i-1]=t//10\n",
    "                        i+=1\n",
    "                        continue\n",
    "                    \n",
    "\n",
    "\n",
    "        def f(i):\n",
    "            v=valid()\n",
    "            if v==-1:\n",
    "                return False\n",
    "            if i==len(wdset):\n",
    "                return v==1\n",
    "            for j in range(0,10):\n",
    "                if j not in visited:\n",
    "                    visited.add(j)\n",
    "                    dt[wd[i]]=j\n",
    "                    if f(i+1):\n",
    "                        return True\n",
    "                    dt[wd[i]]=-1\n",
    "                    visited.remove(j)\n",
    "            return False\n",
    "        return f(0)\n",
    "    \n",
    "    "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
